#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"
#include "TypeDefin.h"

using namespace std;

/*
 *输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。
示例 2：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3
 * */

int count = 0;

//两个先序遍历 todo 这个题是抄的
void dfs(TreeNode *root, int targetSum, long sum) {
    sum += root->val;
    if (sum == targetSum)
        count++;
    if (root->left) dfs(root->left, targetSum, sum);
    if (root->right) dfs(root->right, targetSum, sum);

}

void dfs_tree(TreeNode *root, int targetSum) {
    if (!root)
        return;

    dfs(root, targetSum, 0);
    dfs_tree(root->left, targetSum);
    dfs_tree(root->right, targetSum);
}

int pathSum(TreeNode *root, int targetSum) {
    dfs_tree(root, targetSum);
    return count;
}